蟻本 2-3 01ナップサック問題その2

code: python

n = int(input())

w = list(map(int, input().split()))

v = list(map(int, input().split()))

W = int(input())

dp = [1000000000 * (n * 100 + 1) for i in range(n + 1)]

dp00 = 0

# 価値に対する最小の重さをDPでk

for i in range(n):

for j in range(n * 100):

# 価値の総和のキャパ(j)がi番目の品物の価値(vi)より小さかったら

if (j < vi):

# 対応できないのでそのまま

else:

# i番目の品物が入る前の重さ(dpi[j - vi])にi番目の品物の重さ(wi)を足した場合と、

# i番目の品物を入れなかった場合を比較

dpi + 1j = min(dpij, dpi[j - vi] + wi)

res = 0

for i in range(n * 100):

if (dpni <= W):

res = i

print(res)

# 4

# 2 1 3 2

# 3 2 4 2

# 5

テーマ